//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
//回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 
//
// 
//
// 示例 1： 
//
// 
//输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出：[[1,6],[8,10],[15,18]]
//解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 
//
// 示例 2： 
//
// 
//输入：intervals = [[1,4],[4,5]]
//输出：[[1,5]]
//解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 10⁴ 
// intervals[i].length == 2 
// 0 <= starti <= endi <= 10⁴ 
// 
// Related Topics 数组 排序 👍 1176 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class _56_MergeIntervals {
    public static void main(String[] args) {
        int[][] intervals = new int[][]{{2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}};
        Solution solution = new _56_MergeIntervals().new Solution();
        int[][] res = solution.merge(intervals);
        for (int[] tmp : res) {
            System.out.println(Arrays.toString(tmp));
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return intervals;
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            List<int[]> res = new ArrayList<int[]>();
            for (int i = 0; i < intervals.length; i++) {
                int left = intervals[i][0];
                int right = intervals[i][1];
                if (res.size() == 0 || left > res.get(res.size() - 1)[1]) {
                    res.add(new int[]{left, right});
                } else {
                    res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], right);
                }
            }
            return res.toArray(new int[res.size()][2]);
        }

        /**
         * 错了，不知道为啥
         * @param intervals
         * @return
         */
        public int[][] merge_error(int[][] intervals) {
            if (intervals.length == 0) {
                return intervals;
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            List<Integer[]> res = new ArrayList<Integer[]>();
            int[] one = intervals[0];
            for (int i = 1; i < intervals.length; i++) {
                if (!mergeIn(one, intervals[i])) {
                    res.add(new Integer[]{intervals[i][0], intervals[i][1]});
                }
            }
            res.add(new Integer[]{one[0], one[1]});
            int[][] result = new int[res.size()][2];
            for (int i = 0; i < res.size(); i++) {
                result[i][0] = res.get(i)[0];
                result[i][1] = res.get(i)[1];
            }
            return result;
        }

        public boolean mergeIn(int[] one, int[] another) {
            if (another[1] < one[0] || another[0] > one[1]) {
                return false;
            } else if (another[1] >= one[0] || another[0] <= one[1]) {
                one[0] = Math.min(one[0], another[0]);
                one[1] = Math.max(one[1], another[1]);
                return true;
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}